//
// Created by fh on 2021/7/20.
//

#include "DynamicProgramming.h"


void knapsackProblem() {
    printf("-------------------------------------- 背包问题初级二维数组版 --------------------------------------------\n");
    int weight[] = {2,2,4,6,3}; // 物品重量
    int n = 5; // 物品个数
    int w = 9; // 背包承受的最大重量
    int states[5][10];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (w+1); ++j) {
            states[i][j] = 0;
        }
    }

    for (int i = 0; i < n; ++i) {
        int eachW = weight[i]; // 当前的物品重量
        int j = i-1; // 上一层
        if (j >= 0) {
            for (int k = 0; k < (w+1); ++k) {
                if (states[j][k] == 1) {
                    // 有值
                    int t = eachW + k;
                    if (t <= w) {
                        states[i][t] = 1; // 把第i个物品放入背包
                    }
                    states[i][k] = 1; // 不把第i个物品放入背包
                }
            }
        } else {
            states[i][0] = 1; // 第一个放
            if (eachW <= w) {
                states[i][eachW] = 1; // 第一个不放
            }
        }
    }

    // debug
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (w+1); ++j) {
            printf("%d ",states[i][j]);
        }
        printf("\n");
    }

    printf("---------------------------------\n");
    for (int i = w; i >= 0; --i) {
        if (states[n-1][i] == 1) {
            printf("输出最大重量结果: %d\n",i);
            break;
        }
    }
    printf("\n");
}


void knapsackProblemPro() {
    printf("-------------------------------------- 背包问题初级一维数组版 --------------------------------------------\n");
    int weight[] = {2,2,4,6,3}; // 物品重量
    int n = sizeof(weight)/ sizeof(int); // 物品个数
    int maxW = 9; // 背包承受的最大重量

    int states[maxW+1];
    for (int i = 0; i < (maxW+1); ++i) {
        states[i] = 0;
    }

    for (int i = 0; i < n; ++i) {
        int v = weight[i];
        if (v <= maxW) {
            if (i == 0) {
                states[0] = 1;
                states[v] = 1;
            } else {
                for (int j = 0; j < maxW + 1; ++j) {
                    if (states[j] == 1) {
                        if (v+j <= maxW) {
                            states[v+j] = 1;
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i < (maxW+1); ++i) {
        printf("%d ",states[i]);
    }
    printf("\n");

    printf("---------------------------------\n");
    for (int i = maxW; i >= 0; --i) {
        if (states[i] == 1) {
            printf("输出最大重量结果: %d\n",i);
            break;
        }
    }
}

void wangzhengPro() {
    int items[] = {2,2,4,6,3}; // 物品重量
    int n = 5;
    int w = 9;

    int states[10];
    for (int i = 0; i < 10; ++i) {
        states[i] = 0;
    }
    states[0] = 1; // 第一行的数据要特殊处理，可以利用哨兵优化

    if (items[0] <= w) {
        states[items[0]] = 1;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = w-items[i]; j >= 0; --j) {
            if (states[j] == 1) {
                states[j+items[i]] = 1;
            }
        }
    }

    for (int i = 0; i < 10; ++i) {
        printf("%d ",states[i]);
    }
    printf("\n");

    for (int i = w; i >= 0; --i) {
        if (states[i] == 1) {
            printf("王铮最大值是: %d\n",i);
            break;
        }
    }

}


void knapsackProblemProPro() {
    printf("-------------------------------------- 背包问题升级版 --------------------------------------------\n");
    int weight[] = {2,2,4,6,3}; // 物品重量
    int value[] = {3,4,8,9,6};
    int n = sizeof(weight)/ sizeof(int); // 物品个数
    int maxW = 9; // 背包承受的最大重量

    int states[5][10];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (maxW+1); ++j) {
            states[i][j] = -1;
        }
    }

    for (int i = 0; i < n; ++i) {
        int eachW = weight[i]; // 当前的物品重量
        int j = i-1; // 上一层
        if (j >= 0) {
            // 不选择第i个物品
            for (int k = 0; k < (maxW+1); ++k) {
                if (states[j][k] >= 0) {
                    states[i][k] = states[j][k];
                }
            }
            // 选择第i个物品
            for (int k = 0; k < (maxW + 1); ++k) {
                if (states[j][k] >= 0) {
                    int v = states[j][k] + value[i];
                    if (k+weight[i] <= maxW) { // 这个条件可以放到for循环里面
                        if (v > states[i][k+weight[i]]) {
                            states[i][k+weight[i]] = v;
                        }
                    }
                }
            }
        } else {
            states[i][0] = 0; // 第一个不放
            if (eachW <= maxW) {
                states[i][eachW] = value[0]; // 第一个放
            }
        }
    }

//  debug
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (maxW+1); ++j) {
            printf("%d ",states[i][j]);
        }
        printf("\n");
    }

}


void wangzhengProPro() {
    int weight[] = {2,2,4,6,3}; // 物品重量
    int value[] = {3,4,8,9,6};
    int n = 5; // 物品个数
    int w = 9; // 背包承受的最大重量

    int states[n][w+1];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < w+1; ++j) {
            states[i][j] = -1;
        }
    }
    states[0][0] = 0;
    if (weight[0] <= w) {
        states[0][weight[0]] = value[0];
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= w; ++j) {
            if (states[i-1][j] >= 0) {
                states[i][j] = states[i-1][j];
            }
        }
        for (int j = 0; j <= w-weight[i]; ++j) {
            if (states[i-1][j] >= 0) {
                int v = states[i-1][j] + value[i];
                if (v > states[i][j+weight[i]]) {
                    states[i][j+weight[i]] = v;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < w+1; ++j) {
            printf("%d ",states[i][j]);
        }
        printf("\n");
    }

    int maxValue = -1;
    for (int i = 0; i <= w; ++i) {
        if (states[n-1][i] > maxValue) {
            maxValue = states[n-1][i];
        }
    }

    printf("maxValue: %d\n",maxValue);

}

/* 回溯找零问题求解 */
int innerCash(int n) {
//    printf("%d\n",n);
    if (n == 1 || n == 3 || n == 5 || n < 0) {
//        printf("%d\n",n);
        return 1;
    }
    int a = innerCash(n-1);
    int b = innerCash(n-3);
    int c = innerCash(n-5);

    int min  = (a > b ? b : a);
    min = (min > c ? c : min);
    printf("%d\n",min+1);
    return min + 1;
}
/* 找零问题 */
void changeCash(int n) {
    int result = innerCash(n);
    printf("最少需要:%d个硬币\n",result);
}

/* 动态规划找零问题: 我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 n 元，最少需要多少个硬币 */
void dpChangeCash(int n) {
    int l = n+1;
    int status[l][l];
    for (int i = 0; i < l; ++i) {
        for (int j = 0; j < l; ++j) {
            status[i][j] = 0;
        }
    }
    if (n >= 1) {
        status[1][1] = 1;
    }
    if (n >= 3) {
        status[1][3] = 1;
    }
    if (n >= 5) {
        status[1][5] = 1;
    }
    for (int i = 2; i < l; ++i) {
        for (int j = 1; j < l; ++j) {
            if (status[i-1][j] == 1) {
                if (j+1 <= n) {
                    status[i][j+1] = 1;
                }
                if (j+3 <= n) {
                    status[i][j+3] = 1;
                }
                if (j+5 <= n) {
                    status[i][j+5] = 1;
                }
                if (status[i][n] == 1) {
                    printf("最少需要%d个硬币\n",i);

                    for (int i = 0; i < l; ++i) {
                        for (int j = 0; j < l; ++j) {
                            printf("%d ",status[i][j]);
                        }
                        printf("\n");
                    }

                    return;
                }
            }
        }
    }
    printf("最少需要%d个硬币\n",n);
}

/* dp状态转移表空间降维版 */
void dpProChangeCash(int n) {
    int dp[n+1];
    for (int i = 0; i < n+1; ++i) {
        dp[i] = -1;
    }
    // 支付0元需要0个硬币
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        if (i >= 1 && dp[i-1] >= 0) {
            dp[i] = dp[i-1] + 1;
        }
        if (i >= 3 && dp[i-3] >= 0) {
            dp[i] = dp[i-3] + 1;
        }
        if (i >= 5 && dp[i-5] >= 0) {
            dp[i] = dp[i-5] + 1;
        }
    }
    printf("最少需要%d个硬币\n",dp[n]);
}

/* dp递归加备忘录版 */
int dpProProChangeCash(int n,int array[]) {
    // 状态转移方程 d(n) = min{ d(n-1)+1, d(n-3)+1, d(n-5)+1 }
    if (n == 0) {
        return 0;
    }
    // 使用备忘录，数组作为备忘录保存已经计算好的结果，如果有就直接返回提升递归的效率
    if (array[n] > 0) {
        return array[n];
    }
    int min = -1;
    int one = -1;
    if (n >= 1) {
        one = dpProProChangeCash(n-1,array) + 1;
    }
    if (one != -1) {
        min = one;
    }
    int three = -1;
    if (n >= 3) {
        three = dpProProChangeCash(n-3,array) + 1;
    }
    if (three != -1) {
        if (min > three) {
            min = three;
        }
    }
    int five = -1;
    if (n >= 5) {
        five = dpProProChangeCash(n-5,array) + 1;
    }
    if (five != -1) {
        if (min > five) {
            min = five;
        }
    }
    array[n] = min;
    return min;
}

/* 动态规划demo */
void DPTestDemo() {

    int array[11];
    for (int i = 0; i < 11; ++i) {
        array[i] = -1;
    }
    int a = dpProProChangeCash(4,array);
    printf("%d\n",a);
    return;
//    dpProChangeCash(5);
//    dpChangeCash(20);
//    changeCash(11);
//    wangzhengProPro();
//    knapsackProblemProPro();
    // 背包问题初级二维数组版
    knapsackProblem();
    // 背包问题初级一维数组版
    knapsackProblemPro();

    wangzhengPro();
}